package leetcode_901_1000;

import java.util.Arrays;

public class LeeCode_902 {
    public static void main(String[] args) {
//        System.out.println(atMostNGivenDigitSet(new String[]{"1", "3", "5", "7"}, 100));
        System.out.println(atMostNGivenDigitSet(new String[]{"1", "4", "9"}, 1000000000));
//        System.out.println(atMostNGivenDigitSet(new String[]{"1", "2"}, 2));
    }
    private static int atMostNGivenDigitSet(String[] digits, int n) {
        char[] s = Integer.toString(n).toCharArray();
        char[] dig = new char[digits.length];
        for (int i = 0; i < dig.length; i++) {
            dig[i] = digits[i].charAt(0);
        }
        int[] memo = new int[s.length];
        Arrays.fill(memo, -1);
        return f(s, 0, true, true,  memo, dig) - 1;
    }
    private static int f(char[] s, int i, boolean isLimit, boolean canZero, int[] memo, char[] dig){
        int m = dig.length;
        if (i == s.length){
            return 1;
        }
        if (!isLimit && !canZero && memo[i] != -1){
            return memo[i];
        }
        int up = isLimit ? s[i] : dig[m - 1], res = 0;
        if (canZero){
            res += f(s, i + 1, false, true, memo, dig);
        }
        for (char c : dig) {
            if (isLimit && c > up) {
                break;
            }
            res += f(s, i + 1, isLimit && c == up, false, memo, dig);
        }
        if (!isLimit && !canZero)
            memo[i] = res;
        return res;
    }
}
